\documentclass[12pt]{amsart}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{macros-article}
%\usepackage{fullpage}
\usepackage[all]{xy}
\usepackage{color}
\title{The Generalized Alon Conjecture}
\date{}
\begin{document}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

In the closing remarks of his Memoirs paper, Friedman suggests the following conjecture.

\begin{conjecture*}[Generalized Alon Conjecture]
Fix an \( \epsilon > 0 \) and a \emph{base} graph, \( B \). Then "most" random coverings of degree \( n \) of the base graph have all their "new" eigenvalues at most \( \rho + \epsilon \) where \( \rho \) is the spectral radius of the universal cover of \( B \).
\end{conjecture*}

The notion of "new" eigenvalue simply stems from the idea that if a graph \( G \) is a cover of a base graph \( B \) then the eigenvalues of the base graph all lift as eigenvalues of the cover. Hence we can distinguish the eigenvalues of the cover as being "old" if they are eigenvalues of the base graph and "new" eigenvalues otherwise.

We describe here a model for random coverings of a base graph \( B \). Let \( B \) be a graph whose self-loops, if any, are all whole-loops, with vertex set \( V_B = \{v_1,\ldots,v_s\} \) and oriented edge set \( E_B = \{ e_1,\ldots,e_a \} \). We denote by \( \GnB \) the following model for \( n \)-lifts of the graph \( B \). We obtain an element \( G \) of \( \GnB \) for each choice of \( a \) permutations of \( n \) elements \( \{ \pi_1,\ldots,\pi_a \} \) with the following vertex and oriented edge sets:
\begin{align*}
V_G &= V_B \times \{ 1,\ldots,n \}\\
E_G &= \left\{ \left( (\textrm{tail}(e_j),i), (\textrm{head}(e_j),\pi_j(i)) \right) \mid j=1,\ldots,a \quad i=1,\ldots,n \right\}
\end{align*}

We equip the set \( \GnB \) with a discrete probability by giving a uniform distribution on each of its \( (n!)^a \) elements.

In the case where the base graph is a single vertex with \( d/2 \) whole-loops (for some positive even integer \( d \)) we obtain the \( \Gnd \) model described in Friedman's paper for random \( d \)-regular graphs on \( n \) vertices.

It is in that context that Friedman showed the Alon Conjecture holds by proving the following theorem.

\begin{theorem*}[Old 1.1]
Fix an \( \epsilon > 0 \) and an even positive integer \( d \). Then there is a constant \( c \), such that for a random graph, \( G \), of \( \Gnd \) we have that with probability at least \( 1-c/n^{\tau} \) we have for all \( i > 1 \).
\[
| \lambda_i (G) | \leq 2 \sqrt{d-1} + \epsilon
\]
where \( \tau = \tau_{\text{fund}} = \lceil (\sqrt{d-1}+1)/2 \rceil - 1 \).
\end{theorem*}

The rest of this paper will describe the main elements of Friedman's proofs and suggestions on how to generalize his work in the hope of making some progress on the generalized Alon conjecture.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Trace Method}

An important idea in Friedman's paper consists of looking at the \emph{strongly irreducible trace} of a graph instead of its conventional trace. The main elements are described here.

As much as possible, all the definitions here will be stated for the \( GnB \) model,  where the base graph \( B \) has no half-loops.

\begin{definition}
If \( G \in \GnB \) is a random lift, any walk of length \( k \) on that graph yields a uniquely determined word \( w = \sigma_1 \ldots \sigma_k \) where each \( \sigma_i \) represents one of the oriented edges \( \{ \pi_1, \ldots, \pi_a \} \) of the base graph. Conversely, a walk is uniquely determined by such a word (if it is feasible) and the vertex of the graph \( G \) at which it starts (actually, the height of the vertex is enough since we know it projects to \( \tail(\sigma_1) \) on the base graph).

A walk \( w = \sigma_1 \ldots \sigma_k \) is said to be \emph{irreducible} if \( \sigma_i \neq \sigma_{i+1}^{-1} \) for all \( i = 1, \ldots, k-1 \), that is if the walk is never back-tracking. And is said to be \emph{strongly irreducible} if additionally we have that \( \sigma_1 \neq \sigma_k^{-1} \).
\end{definition}

Recall that the trace of the \( k^{\text{th}} \) power of the adjacency matrix of a graph is the number of closed walks in that graph, we expand that notion here.

\begin{definition}
Let \( G \) be a graph, denote by \( \SIT(G;k) \) the number of strongly irreducible closed walks of length \( k \) in the graph \( G \). We can construct a graph \( G_{\text{Irred}} \) whose vertices are the oriented edges of the graph \( G \) and where there is a directed edge from vertex \( e_1 \) to vertex \( e_2 \) if \( e_1e_2 \) is an irreducible path (that is, the oriented edges \( e_1 \) and \( e_2 \) are not opposite of each other). Then closed walks in the graph \( G_\text{Irred} \) correspond to strongly irreducible closed walks in \( G \), the original graph. This leads naturally to ask about the eigenvalues of the adjacency matrix of \( G_\text{Irred} \), called the \emph{Hashimoto matrix} of the graph \( G \).
\end{definition}

\begin{lemma*}
Let \( G \in \Gnd \) be a \( d \)-regular graph on \( n \) vertices, let \( \lambda \) be an eigenvalue of the graph \( G \), and set
\[
\mu_{1,2} (\lambda) = \frac{\lambda \pm \sqrt{\lambda^2 - 4(d-1)}}{2}
\]
Then we can describe the eigenvalues (with multiplicities) of the Hashimoto matrix as follow: For each eigenvalue \( \lambda_i \) of the graph \( G \) we have the eigenvalues \( \mu_1(\lambda_i) \) and \( \mu_2(\lambda_i) \) each with multiplicity 1 and the eigenvalues 1 and -1 each with multiplicity \( (d-2)/2 \). Hence we have
\[
\SIT(G;k) = \sum_{i=1}^n \left[\mu_1(\lambda_i)^k + \mu_2(\lambda_i)^k + (1 + (-1)^k)\frac{(d-2)}{2}\right]
\]
\end{lemma*}

The Hashimoto eigenvalues have very interesting properties which are crucial in the proof of the Alon conjecture. First, the following theorem shows that if the eigenvalues of a \( d \)-regular graph are bounded away from their largest (Perron-Frobenius) eigenvalue, then the Hashimoto eigenvalues will do so as well.

\begin{theorem*}[Old 10.5]
Fix an integer \( d > 2 \) and a real number \( \epsilon > 0 \). Then there is an \( \epsilon' > 0 \) such that if \( G \in \Gnd \) is a \( d \)-regular graph with the property that
\[
\lambda_1 = d \quad \text{and}\quad | \lambda_i| \leq d - \epsilon \quad \text{for all } i = 2, \ldots n
\]
then the corresponding Hashimoto eigenvalues satisfy
\[
\mu_1(\lambda_1) = d-1, \quad \mu_2(\lambda_1) = 1
\]
and
\[
| \mu_j(\lambda_i) | \leq d-1-\epsilon' \quad \text{for all } i=2, \ldots, n \text{ and } j=1,2
\]
\end{theorem*}

Conversely, we can use Hashimoto eigenvalues to estimate the behaviour of the adjacency eigenvalues.

\begin{theorem*}[claim on page. 89]
Fix an \( \epsilon > 0 \) then there exists an \( \eta > 0 \) such that \( | \lambda | \geq 2 \sqrt{d-1} + \epsilon \) implies that there exists \( j \) such that \( | \mu_j(\lambda) | \geq e^\eta \sqrt{d-1} \).
\end{theorem*}

This gives us access to proving the Alon Conjecture. If \( C \) is the event
\[
C = \{ G \in \Gnd \mid |\lambda_i| < 2\sqrt{d-1} + \epsilon \text{ for } i=2,\ldots, n \}
\]
and \( B \) is the event
\[
B = \{ G \in \Gnd \mid |\mu_j(\lambda_i) | \geq e^\eta \sqrt{d-1} \text{ for some } j \in \{1,2\} \text{ and } i \neq 1 \}
\]
Then the previous claim means that \( C^c \subseteq B \) and hence we only need to show that \( \Prob(B) = O(n^{-\tau}) \). This cannot be shown directly, instead, we make another two assumptions, which constitute the event \( A \)
\[
A = \{ G \in \Gnd \mid \chi_\Psi(G) = 0 \text{ and } |\mu_j(\lambda_i)| \leq d-1-\epsilon', \,\forall j\forall i\neq 1 \}
\]
We will discuss the random variable \( \chi_\Psi \) below in the section on tangles. Before this, let us indicate why we can make this assumption. Friedman proves the following two theorems with regard to magnification. It is actually irrelevant here what the definition of a \( \gamma \)-spreader is, what matters is that those have the property describe in the following theorem.

\begin{theorem*}[Old 12.2]
Let \( G \) be a \( d \)-regular \( \gamma \)-spreader. Then for all \( i > 1 \) we have
\[
\lambda_i^2(G) \leq d^2 - \frac{\gamma^2}{4+2\gamma^2}
\]
\end{theorem*}

And in the \( \Gnd \) model, we can show that this occurs with a good probability.

\begin{theorem*}[Old 12.3]
For any \( \epsilon > 0 \) and even \( d \geq 4 \) there is a \( \gamma > 0 \) such that \( G \in \Gnd \) is a \( \gamma \)-spreader with probability \( 1-O(n^{-\tau} ) \).
\end{theorem*}

Hence, combined with the Old theorem 10.5 we are guaranteed that event \( A \) holds with probability at most \( 1-O(n^{-\tau}) \) and since
\[
\Prob(B) = \Prob(A \cap B) + \underbrace{\Prob (A^c \cap B)}_{\leq O(n^{-\tau})}
\]
we only need to show that \( \Prob(A \cap B) = O(n^{-\tau}) \).

Before we continue, let us introduce tangles and the meaning of the \( \chi_\Psi(G) = 0 \) assumption.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Tangles}

Friedman noticed that for a random lift \( G \in \Gnd \) to contain some specific subgraphs will be an obstruction to the desired bound on their second largest eigenvalue. Let us describe that obstruction more precisely.

\begin{definition}
Let \( \psi \) be a finite connected graph with maximum degree at most \( d \) (but not \( d \)-regular). We denote by \( \Tree_d(\psi) \) the universal cover in the category of \( d \)-regular graphs with a \( \psi \) inclusion. This always yields an infinite graph and we denote by \( \lambda_1(\Tree_d(\psi)) \) its spectral radius.
\end{definition}

\begin{theorem*}[Old 4.2]
Fix a positive integer, \( d \geq 3 \), and a finite connected graph \( \psi \). Any \( d \)-regular graph \( G \) on \( n \) vertices that contains \( \psi \) has second eigenvalue at least \( \lambda_1(\Tree_d(\psi)) - o(1) \).
\end{theorem*}

To understand where the obstruction lies, we need to understand how the spectral radius of \( \Tree_d(\psi) \) behaves. The following theorem gives a very precise description of that behaviour.

\begin{theorem*}[Old 3.13]
Let \( d \geq 3 \), and let \( \psi \) be a finite connected graph with each vertex of degree at most \( d \). Then
\begin{align*}
\lambda_1(\Tree_d(\psi)) = 2\sqrt{d-1} &\iff \lambda_{\Irred} (\psi) \leq \sqrt{d-1}\\
\lambda_1(\Tree_d(\psi)) > 2\sqrt{d-1} &\iff \lambda_{\Irred} (\psi) > \sqrt{d-1}
\end{align*}
Where the \emph{irreducible eigenvalue,} \( \lambda_{\Irred} (\psi) \), is the largest Hashimoto eigenvalue of the graph \( \psi \).
\end{theorem*}

From this, we can conclude that containing a graph whose irreducible eigenvalue is larger than \( \sqrt{d-1} \), will eventually give rise to random lifts who do not match the desired bound on their second largest eigenvalue.

\begin{definition}
A graph is called a \emph{tangle} if its irreducible eigenvalue is at least \( \sqrt{d-1} \) (Friedman called those supercritical tangles). A tangle is a \emph{critical tangle} if its irreducible eigenvalue is precisely \( \sqrt{d-1} \) and it is a \emph{hypercritical tangle} otherwise. The \emph{order} of a tangle is
\[
\ord(\psi) = |E_\psi | - |V_\psi |
\]
Note that for a connected graph, the order is at least -1 (and is precisely -1 if and only if the graph is a tree).
\end{definition}

A counting argument allows us to estimate the number of occurrences of a fixed tangle in a random lift.

\begin{theorem*}[Old 4.7]
Let \( \psi \) be a tangle of non-negative order \(r \). Then the expected number of occurrences of \( \psi \) in an element, \( G \), of \( \Gnd \) is \( n^{-r} + O(n^{-r-1}) \). The probability that at least one occurrence occurs is at least
\[
\frac{n^{-r}}{c} - \frac{n^{-2r}}{2c^2} + O(n^{-r-1})
\]
where \( c \) is the number of automorphisms of the complete pruning of \( \psi \).
\end{theorem*}

Despite the appearances of Old theorem 3.13, both types of tangles are problematic to our approach and need to be removed. We would like to consider the event where a random lift \( G \) does not contain any tangle. In order to do this, we need some guarantees of finiteness, granted by the following theorem.

\begin{theorem*}[Old 9.2]
The set of tangles of order at most \( r \) that are minimal with respect to inclusion, denote by \( \Psi_{\text{min}}[ r ] \), is finite.
\end{theorem*}

So if \( \Psi \) is the set of tangles of order less than \( r \) that are minimal with respect to inclusion, and if \( \chi_\Psi \) is the indicator function of the event that an element \( G \) of \( \Gnd \) contains a tangle from \( \Psi \), i.e.,
\[
\chi_\Psi (G) = \begin{cases}
1 & \text{if } G \text{contains a tangle from } \Psi,\\
0 & \text{if not}
\end{cases}
\]
then the previous results show that
\[
\Prob(\chi_\Psi = 1) = O(n^{-\tau})
\]
where \( \tau \) is the smallest order of a tangle and which can be show satisfies
\[
\tau = \lceil (\sqrt{d-1}+1)/2 \rceil - 1
\]

Avoiding tangles is a crucial step but not the last one. In order to be able to estimate the strongly irreducible trace and so the probability of the event \( A \cap B \), we need to describe a strategy for making this estimate. This is accomplished using \emph{forms} and \emph{types} and is described in the next two sections.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Walk sums expansions}

\begin{definition}
A \emph{$(k,n)$-walk} is a pair $(w;\vec {t}\,)$ where $w$ is called the \emph{base walk} and $\vec t$ the \emph{trajectory}. The base walk $w=\sigma_1\ldots\sigma_k$ is an oriented walk of length $k$ in the base graph $B$, where the $\sigma_i$ denote oriented edges of the base graph. The trajectory $\vec t = \left( (v_0,t_0), (v_1,t_1), \ldots, (v_k,t_k) \right)$ is an ordered $k+1$-tuple of pairs $(v_i,t_i)$ where $v_i$ is a vertex of the base graph and $t_i$ an integer between 1 and $n$. Additionally, $(k,n)$-walks are required to satisfy the following feasibility conditions:
\begin{itemize}
\item For all $i=1,\ldots,k$ we have $\textrm{tail}(\sigma_i) = v_{i-1}$ and $\textrm{head}(\sigma_i)=v_i$,
\item if $\sigma_i=\sigma_j$ then $t_{i-1}=t_{j-1}$ if and only if $t_i=t_j$,
\item if $\sigma_i=\sigma_j^{-1}$ then $t_{i-1}=t_j$ if and only if $t_i=t_{j-1}$.
\end{itemize}
We call $k$ the \emph{length} of the walk and $n$ its \emph{size}. The length of a walk is uniquely determined, but not its size. We say that the walk is \emph{closed} if the base walk $w$ is and if $t_0=t_k$. We say that the walk is \emph{irreducible} if the base walk $w$ is an irreducible (or non-backtracking) walk.
\end{definition}

The idea of that definition is that any walk in a random element $G$ of $\mathcal{G}_{n,B}$ is the lift of some walk in the base graph --encoded by the base walk $w$-- and the trajectory $\vec t$ describes the vertices of that graph $G$ visited by the walk. The conditions added in the definition ensure that the walk will exist in at least one of the random element of the $\mathcal{G}_{n,B}$ model and we denote by $P(w;\vec{t}\,)$ the probability of that event.

\begin{note}
\textit{Recall that a random element of the $\mathcal{G}_{n,B}$ model is entirely described by the choice of a $n$-permutation $\pi_j$ for each edge of the base graph. As a consequence the probability that a $(k,n)$-walk $(w;\vec t\,)$ is realizable in a random element simply corresponds to the probability that the permutation $\pi_j$ are chosen such that $\sigma_j(t_{j-1})=t_j$.}
\end{note}

\begin{remark}
We can view the trace of the $k$-th power of a random element of the $\mathcal{G}_{n,B}$ model as a random variable, for which we have
\[
\textrm{Tr}(G^k) = \sum_{(w;\vec t\,) \in \mathcal{W}} P(w;\vec t\,)
\]
where $\mathcal{W}$ is the collection of all closed $(k,n)$-walks based on $B$.
\end{remark}

\begin{definition}
Given a base walk $w$, we define an equivalence relation on all trajectories $\vec t$ that make $(w;\vec t\,)$ a $(k,n)$-walk as follow: let $\vec t = \left( (v_0,t_0), (v_1,t_1), \ldots, (v_k,t_k) \right)$ and $\vec s = \left( (v_0,s_0), (v_1,s_1), \ldots, (v_k,s_k) \right)$ be two such trajectories, then we say they \emph{differ by a symmetry} if there exists a $n$-permutation $\sigma$ such that $\sigma(t_i) = s_i$ for all $i = 0,\ldots,k$. We denote by $[\vec t\,]_n$ the associated equivalence class.
\end{definition}


\begin{definition}
A \emph{walk collection}, $\mathcal{W} = \{ \mathcal{W}(k,n) \}_{k,n \geq 1}$ is a collection where for any two positive integers $k$ and $n$ the elements of the set $\mathcal{W}(k,n)$ are $(k,n)$-walks satisfying the following conditions.
\begin{itemize}
\item \textbf{Symmetry:} The walk collection contains all trajectories that differ by a symmetry; that is, if $(w;\vec t\,) \in \mathcal{W}(k,n)$ then $(w;\vec s\,) \in \mathcal{W}(k,n)$ for all $\vec s \in [\vec t\,]_n$.
\item \textbf{Size invariance:} The walk collection reflects the fact that the size of a walk isn't uniquely determined; that is, if $(w;\vec t\,) \in \mathcal{W}(k,n)$ then $(w;\vec t\,) \in \mathcal{W}(k,m)$ for all $m \geq \max\{ t_i \mid \vec t = \left( (v_0,t_0), (v_1,t_1), \ldots, (v_k,t_k) \right) \}$
\item \textbf{Irreducible walks:} All the walks in the walk collection have to be irreducible; that is, the base walk $w$ of any $(k,n)$-walk in the collection has to be irreducible.
\item \textbf{Closed walks:} All the walks in the walk collection have to be closed; that is, the base walk $w$ of any $(k,n)$-walk $(w;\vec t\,)$ in the collection has to be closed and its trajectory must satisfy $t_0 = t_k$.
\end{itemize}
Given a walk collection $\mathcal{W}$ its associated \emph{(k,n)-walk sum} is
\[
\textrm{WalkSum}(\mathcal{W},k,n) = \sum_{(w;\vec t\,) \in \mathcal{W}(k,n)} P(w;\vec t\,)
\]
Note that this sum is always a finite sum (unless the base graph $B$ has infinitely many edges). Since walk collections are symmetric, we can regroup the terms of the above sum by grouping trajectories that differ by a symmetry. Let
\[
\text{E}_\text{symm}(w;\vec t\,)_n = \sum_{\vec s \in [\vec t \, ]_n} P(w;\vec s\,)
\]
then we have
\[
\textrm{WalkSum}(\mathcal{W},k,n) = \sum_{(w;[\vec t\,]_n) \in \mathcal{W}(k,n)} \text{E}_\text{symm}(w;\vec t\,)_n
\]
\end{definition}

Let us now comment about the probability of a given walk. Let $(w;\vec t\,)$ be a closed $(k,n)$-walk. Denote by \emph{$a_j$} the number of values of the corresponding permutation $\pi_j$ that the conditions $\sigma_i(t_{i-1})=t_i$ involve determining in order for the walk to be feasible; and denote by \emph{$b_i$} the number of vertices in the trajectory that belong to the fibre of the $i^\text{th}$ vertex of the base graph $B$, then
\begin{align*}
P(w;\vec t\,) &= \prod_{j=1}^a \frac{(n-a_j)!}{n!} \\
\intertext{and}
\#[\vec t\,]_n &= \prod_{i=1}^s \frac{n!}{(n-b_i)!} \\
\intertext{and so we can conclude that}
\text{E}_\text{symm}(w;\vec t\,)_n &= \prod_{i=1}^s \frac{n!}{(n-b_i)!} \prod_{j=1}^a \frac{(n-a_j)!}{n!}
\end{align*}
We can denote by $\emph{e}=a_1+ \ldots +a_a$ and $\emph{v}=b_1 + \ldots + b_s$ and $e$ is the number of edges of the walk and $v$ its number of vertices.

\begin{definition}
Given a $(k,n)$-walk as above, its \emph{order} is $e-v$.
\end{definition}

\begin{theorem*}[Old 5.5]
There exists polynomials $p_i=p_i(a_1,\ldots,a_a,b_1,\ldots,b_s)$ for all $i \geq 0$ such that
\[
\text{E}_\text{symm}(w;\vec t\,)_n = \frac{1}{n^{e-v}} \sum_{i \geq 0}p_i(a_1,\ldots,a_a,b_1,\ldots,b_s) \frac{1}{n^i}
\]	
and for any integer positive integer $q$ we have
\[
\text{E}_\text{symm}(w;\vec t\,)_n = \frac{1}{n^{e-v}} \left( p_0 + \frac{p_1}{n} + \ldots + \frac{p_{q-1}}{n^{q-1}} + \frac{\textnormal{error}}{n^q} \right) 
\]
where
\[
|\textnormal{error}| \leq e^{qk/(n-k)}k^{2q}
\]
\end{theorem*}

\begin{lemma*}[Old 5.7]
Given a closed base word $w$ of length $k$, we have that
\[
\sum_{\vec t \text{ such that } (w;\vec t\,) \text{ is of order }\geq r} \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! P(w;\vec t\,) \leq n \binom{k}{r+1}\left(\frac{k}{n-k}\right)^{r+1}
\]
which, for $k \leq n/2$ is at most $ck^{2r+2}n^{-r}$ for some constant $c$ depending only on $r$.
\end{lemma*}

\begin{lemma*}[Old 5.8]
Let $w$ be an irreducible base walk of length $k$, then
\[
\# \left\{ [\vec t\,]_n \mid (w;\vec t\,) \text{ is of order less than }r \right\} \leq \sum_{i=0}^r \binom{k}{i}k^i \leq ck^{2r}
\]
\end{lemma*}

\begin{theorem*}[Old 5.9]
Let $\mathcal{W}$ be a walk collection and let $r$ be a positive integer, then for all $k \leq n/2$ we have
\[
\textrm{WalkSum}(\mathcal{W},k,n) = f_0(k) + \frac{f_1(k)}{n} + \ldots + \frac{f_{r-1}(k)}{n^{r-1}} + \frac{\textrm{error}}{n^r}
\]
where
\[
f_i(k) = \sum_{j=0}^{r-1} \sum_{(w;[\vec t\,]) \text{ of order }j, \in \mathcal{W}(k,n)} p_{i-j}(w;[\vec t\,])
\]
\end{theorem*}

This last theorem is the basis for our work with the strongly irreducible trace. We would like to show how to deal with tangles, for this, we need to arrange the different walks by patterns that Friedman calls new types.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Forms, Types and New Types}

\begin{definition}
The \emph{form}, \( \Gamma = \Gamma(w;\vec t) \), of a \( (k,n) \)-walk is the subgraph traced out by the walk with the following additional information: We remember the order in which the vertices and the edges are visited and the direction each edge is first traversed.
\end{definition}

We would like to expand that notion by forgetting more information about the subgraph traced out by a walk and only focus on its general shape, that we call its \emph{type}. For this, we will remove all the vertices of degree 2. In this case edges might represent paths and so we can think of the edges of a type of having different lengths. A \emph{lettering} of a type is the assignment to each directed edge of a starting letter and an ending letter (in \( \Pi \), the alphabet of oriented edges of the base graph). By making a distinction between the edges of a type we allow ourselves to precisely focus on where tangles might occur.

\begin{definition}
A \emph{\( B \)-new type} is a lettered type and a partition of its edges into two sets: the \emph{long} edges and the \emph{fixed} edges. Fixed edges have assigned length less than the integer \( B \) and long edges have unassigned lengths at least \( B \). Furthermore, we actually require to know the precise path on each fixed edge (given by a word in \( \Pi \) of the appropriate length.
\end{definition}

Those definitions are of course workable in the sense that there are always finitely many types (up to isomorphism) of a fixed order \( r \) and that given a type \( T \) and an integer \( B \), there are always finitely many \( B \)-new types based on the type \( T \).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Selective Trace}

From this, we can now define a refinement of our trace.

\begin{definition}
Let \( \Psi \) be a set of tangles and let \( S \) be an integer. We say that a walk is \emph{\( (S,\Psi) \)-selective} if it has no subpath of length at most \( S \) that traces out a tangle in the set \( \Psi \). We denote by \( \SSIT_{S,\Psi}(G;k) \) the number of \( (S,\Psi) \)-selective strongly irreducible closed walks of length \( k \) in the graph \( G \).
\end{definition}

In the proof of the Alon Conjecture, Friedman uses the assumption that \( \chi_\Psi = 0 \) in order to guarantee that the usual strongly irreducible trace is the same as the selective one. It is in the context of selective traces that we are able to prove that if we fix a lettered \( B \)-new type and describe how many times the long and fixed edges are traversed, then we can bound the number of closed selective walks in any form of that type. From there, we can prove the following crucial theorem.

\begin{theorem*}[Modified Old 9.3]
Let \( \Psi \) be a finite set of pruned (nonempty) tangles of order at least 1. Let \( \chi_\Psi \) be the indicator function of the event that an element \( G \) of \( \Gnd \) contains a tangle from \( \Psi \). Let \( \Psi' \) be a set of tangles including all supercritical tangles of order less than \( r \). Then for any \( r \) there is an \( S_0(r,\Psi,\Psi') \) such that for all \( S \geq S_0 \) we have an expansion
\[
E[\chi_\Psi \IrSelTr_{S,\Psi'}(G;k)] = f_0(k) + \frac{f_1(k)}{n} + \ldots + \frac{f_{r-1}(k)}{n^{r-1}} + \frac{\text{error}}{n^r},
\]
where the \( f_i \) are \( d \)-Ramanujan and the error term satisfies
\[
| \text{error} | \leq ck^{\tilde{r}}(d-1)^k
\] 
with \( c \) and \( \tilde{r} \) depending only on \( r, \Psi \text{ and } \Psi' \). And the same holds if we substitute \( (1- \chi_\Psi) \) instead of \( \chi_\Psi \).
\end{theorem*}

The following technical theorem will be combined to 9.3 to estimate the probability of event \( A \cap B \) and conclude Friedman's proof.

\begin{theorem*}[Old 11.1]
Fix integers \( r, \tilde{r}, d \) with \( d > 2 \), polynomials \( p_0, \ldots, p_r \) a constant \( c \) and an integer \( D \). Assume that for each \( n \) we have complex-valued random variables \( \theta_1, \ldots, \theta_m \) such that \( m = Dn \). Assume that \( 1-\theta_i \) is of absolute value at most 1, and is purely real if its absolute value is greater than \( (d-1)^{-1/2} \). Furthermore assume that for all integers \( k \geq 1 \) we have
\[
E\left[ \sum_i (1-\theta_i)^k \right] = \sum_{j=0}^{r-1} \frac{p_j(k)}{n^j} + O\left( \frac{k^{\tilde{r}}}{n^r} + \frac{k^c}{(\sqrt{d-1})^k} \right)
\]
Then for sufficiently large \( n \) we have
\[
E \left[ \sum_i \chi_{\left\{ |\theta_i| > \log^{-2}(n) \right\}} (1-\theta_i)^k \right] = O \left( \frac{Dn}{n^{r/3}} + \frac{k^c}{(\sqrt{d-1})^k} \right)
\]
for all \( k \) with \( 1 \leq k \leq n^\gamma \) for some constant \( \gamma > 0 \), where the constant \( \gamma \) and the constant in the \( O(\cdot) \) notation depends only on \( r, \tilde{r}, d \) and the maximum degree of the \( p_i \).
\end{theorem*}

We do not show the details here, but this is enough to easily deduce values for \( k \) and \( r \) to be used to estimate that the probability of the event \( A \cap B \) is \( O(n^{-\tau}) \) and conclude the proof of the Alon Conjecture.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Future work and questions}

Generalizing Friedman's work seems possible, if only in the case of a regular, Ramanujan base graph. Several interesting questions emerge in an attempt to generalize some crucial results. We describe some of them here briefly.

\subsection*{Tangles}

The obstruction represented by tangles is interesting to generalize. Theorem 3.13 can be described as follow: given that the base graph in the \( \Gnd \) model is the single vertex with \( d/2 \) whole-loops and that its universal cover is the \( d \)-regular infinite tree that has a spectral radius of \( 2 \sqrt{d-1} \) one can do the following thing: take a graph that is a tangle candidate (that is, having maximum degree at most \( d \) while not being \( d \)-regular, or in other words, being a subgraph of a random lift in \( \Gnd \) ) and complete it as an infinite graph using the natural continuation of edges as in the universal cover. Then two cases arise: either this new infinite graph has the same spectral radius as the infinite \( d \)-regular tree or it is larger. Hypercritical graphs are of that kind and can be described in terms of their irreducible eigenvalues. From the irreducible eigenvalue case we see that there is a boundary case, the critical tangles, that needs to be considered as well.

We can generalize this by performing the same operation: Consider a graph \( \psi \) which is a subgraph of some random lift a base graph \( B \). Complete it into an infinite tree following the patters described by the universal cover of the base graph (as Friedman wrote, this is the universal cover in the category of lifts of the base graph which have a \( \psi \) inclusion. We denote this infinite graph by \( \Tree_B(\psi) \). Then it seems that the spectral radius of that graph should be either \( \rho \), the spectral radius of the universal cover of the base graph, or larger than that, in which case we will say that the graph \( \psi \) is a \( B \)-tangle (or simply a tangle).

The question which arises is as follow: can we always describe \( B \)-tangles in terms of their irreducible eigenvalues? Can we understand from this perspective whether critical tangles necessarily have to be considered as well (and if so, how to describe them in this context).

It seems that in the case of a regular base graph there is enough symmetry to allow for similar computations that Friedman performed in his proof of theorem 3.13.

It also seems natural that theorem 4.2 should be generalized easily.

\subsection*{Strongly Irreducible Trace}
In the case of a general base, it is not immediately clear how much control one will have on the Hashimoto eigenvalues. Friedman's proof heavily relies on some subtle properties of these eigenvalues, in particular that an adjacency eigenvalue that is larger or equal than the desired bound of \( 2 \sqrt{d-1} + \epsilon \) will yield a similar obstruction in the sense that at least one of the corresponding Hashimoto eigenvalue will be at least \( e^\eta \sqrt{d-1} \) for some \( \eta >0 \) which only depends on \( \epsilon \) and furthermore that in this case, the Hashimoto eigenvalue has to be a real number.















\end{document}